#pragma once


//哈希函数 hash(key)=key%capacity    capacity=10

//研究表明,当表的长度为质数且表装载因子 a 不超过 0.5 的时候,新的表项一定能够插入,而且任何一个位置都不会被探查两次.因此只要表中有一半的空位置,就不会存在表满的问题.在搜索时可以不考虑表装满的情况
//但是在插入的时候表的装载因子 a 不能超过 0.5(如果查出必须考虑增增容)

//查找的时候就是遇见空就停止,但是如果删除中间的元素后,在中间的位置遇见空还是会停止
//所以要避免这种情况就需要用状态值来进行标记
//可以暂时的把闭散列的哈希表想成一个数组,数组就是要存放那些待插入的元素,元素的下标位置,就是通过哈希函数来确定的(除留余数法)



//哈希表的实现
#include<iostream>
#include<vector>
using namespace std;


enum status//   status 身份,低位,重视程度
{
    //枚举中的常量的可读性是非常强的
    //这三个就是状态的标记,遇见空的就停止,遇见删除不停止,继续往后查找
    EXIST,//存在
    EMPTY,//空的
    DELETE//删除
};

template<class K,class V>//前面的先简单的实现一下,后面封装的时候再去增加模板参数
struct HashData
{
public:
    HashData()
    :_status(EMPTY)
    {}

    pair<K,V>_kv;
    status _status;
};



//resize 会分配 vector 的容器的容量,并且进行初始化

template<class K,class V>//新增加最后一个元素的情况下就可以同时封装 map 和 set 了,也就是这样 template<class K,class V,class KeyOFT>
class HashTable
{
public:
    //------------------------------往哈希表中插入值-----------------------------------------------------------------------------------
    bool insert(const pair<K,V>& kv)
    {
        //-----------------------------------------------线性探测解决问题-----------------------------
//        size_t start=kv.first % _tables.size();//一定要模上容器的实际大小,而不是 capacity,这两个有本质的区别
//        size_t i=0;
//        size_t index=start+i;//index:索引,下标

        ////探测可能不止一次
        ////如果连续位置冲突比较多,容易引起踩踏洪水效应
//        while(_tables[index]._status==EXIST)//遇见空的或者删除就会停止      第一次探测就是当前的位置,如当前的位置满了,或者已经存在了,那么就探测下一个位置
//        {
//            ++i;
//            index=start+i;
//            index%=_tables.size();//在哪个数组中循环,总要找到一个空位置进行存储
//        }
//
//        //能出循环就是找到了一个空位置
//        _tables[i]._kv=kv;//找到了空位置就要进行插入
//        _tables[i]._status=EXIST;//这个是当前元素空间的状态
//        ++_n;//这个 vector 容器中又新增了一个元素


        //-------------------------二次探测解决问题--------------------------------------------------
        //二次探测就是用的 i 就是 i的平方,而不是单纯的 i
        //二次探测只是缓解了一次探测的问题,但是并不是全部解决
        //线性探测中没有演示载荷因子的使用,只是在二次探测中展示了载荷因子的使用


        //------------------------哈希表在什么样的情况下才能扩容-----------------------------
        //ps1:散列表的(哈希表)载荷因子定义为 a=填入表中的元素个数/散列表的长度                         -----其实就数组的满员率
        //ps2:a 是散列表装满程度的标志因子.由于表长是定值,a 与"填入表中的元素个数成正比",所以 a 越大,表明填入表中的元素越多,产生冲突的可能性也就越大;反之 a 越小,表明填入表中的元素越少,产生冲突的可能也就越小
        //---实际上,散列表的平均查找长度是载荷因子 a 的函数,只是不同处理冲突的方法有不同的函数
        //ps3(了解):对于开放定址法,载荷因子是特别重要的因素,应该严格限制在 0.7-0.8 以下,超过 0.8 以后,查表时的 cpu 缓存不命中按照质数曲线上升.
        //--就像 java 中的系统库将 a 限制为 0.75,如果超过了这个值,将会 resize 散列表

        //---------这个判断是用来查看是否需要扩容的
        if(_tables.size()==0 || _n*10/_tables.size()>=7)//当然也可以强制类型转化乘浮点数和 0.7 进行比较
        {
            //满足了这个条件就会进行扩容  ps1:负载因子越小冲突的概率低,效率越高   ps2:但是效率越高,空间浪费越多,空间利用率高了,效率也就低了,甚至可能会造成死循环的情况
            size_t newsize=_tables.size()==0?10:_tables.size()*2;
            //但是不能直接在原表的基础上直接进行扩容,原来的数模上 x 和 2x 是不一样的
            HashTable<K,V>newtable;
            newtable._tables.resize(newsize);
            for(size_t i=0;i<_tables.size();++i)
            {
                if(_tables[i]._status==EXIST)
                {
                    newtable.insert(_tables[i]._kv);//新的表中进行插入用的还是现在的这个插入成员函数
                }
            }
            _tables.swap(newtable._tables);//可以理解为两个表中的容器进行了交换,并且在这个插入函数结束的时候,这个函数的生命周期就结束了,也算一举两得
        }


        size_t start=kv.first % _tables.size();//一定要模上容器的实际大小,而不是 capacity,这两个有本质的区别
        size_t i=0;
        size_t index=start;//index:索引,下标
        while(_tables[index]._status==EXIST)
        {
            ++i;
            index=start+(i*i);//也就是说会跳的更远的
            index%=_tables.size();
        }
        _tables[index]._kv=kv;//找到了空位置就要进行插入
        _tables[index]._status=EXIST;//这个是当前元素空间的状态
        ++_n;//这个 vector 容器中又新增了一个元素
        return true;
    }
    //-----------------------------------------------------插入函数结束了---------------------------------------------------------------------------------------
private:
    vector<HashData<K,V>> _tables;//可以说哈希表每个元素都是一个结点    //哈希表中是用容器来实现的,然后容器中存放的是键值对的形式         //table:表
    size_t _n=0;//有效数据的个数
};